Self-routing packet switching networks with multiple paths through the network are known. These self-routing networks have a plurality of paths but are not nonblocking from any given input port to an output port. One such system is described in U.S. Pat. No. 4,550,397, by J. S. Turner, et al. The latter describes a system in which switching network nodes automatically determine an alternate route through a switching network so as to increase reliability and distribute traffic. The switching network comprises stages of distribution and routing nodes. The routing nodes are responsive to physical addresses associated with the packets to communicate those packets to address designated downstream nodes. The distribution switching nodes statistically communicate packets to downstream switching nodes on the basis of an alternate routing algorithm and availability of downstream nodes. The initial network stages are alternate distribution and routing stages followed by only routing stages for the remaining stages of the network.
The previously described packet switching network of Turner only allows the communication of packets through the switching network. Circuit switching requires a path to remain setup for an indefinite period of time, and the network described by Turner cannot perform this type of operation because a large portion of the paths would become blocked.
Another packet switching network is described in the application of C. A. Lea and W. A. Montgomery, "A Self-Routing Packet Switching Network with Intra-Stage Packet Communication," Ser. No. 654,763, filed Sept. 26, 1984. This application discloses a packet switching network in which self-routing packets are communicated through the network by intra-communication of the packets within a stage as well as inter-communication of packets among stages. The stages each have a plurality of pairs of switch nodes with each pair having an intranode link between the pair of nodes. Each of the switch nodes comprise input controllers and output controllers. The input controller of a node is responsive to the receipt of a packet for interrogating the address field of the packet to determine the destination of the packet. That input controller, on the basis of the destination determination, communicates the packet towards the destination via either an inter-stage link or an intranode link on the basis of availability of the links and an internal control circuit.
A switching network for providing both packet and circuit switched information communication is described in the application of C. A. Lea, "Multiple Paths in a Self-Routing Packet and Circuit Switching Network," Ser. No. 654,765, filed Sept. 26, 1984. This self-routing network has a plurality of stages and the stages are interconnected by links. Each pair of switch nodes within a given stage share the same set of input links from the preceding stage. In response to the receipt of address information from an originating interface controller transmitted via a link, a pair of nodes determine one of a multitude of paths through the switching network by one of the pair responding to the address information to communicate the address information to the next sequential stage after establishing a path through that particular switch node. Once a path has been established through the switch node, an acknowledge signal is transmitted back to the network from the destination trunk controller indicating that a path has been established. The path remains established until the end field of the packet is detected or the proper end information is transmitted after the transmission of the circuit switched information.
Nonblocking networks are known. The simplest of nonblocking networks that is capable of interconnecting N.sub.1 input terminals and N.sub.2 output terminals uses a rectangular N.sub.1 .times.N.sub.2 array of switching elements or crosspoints. Although such a rectangular array is nonblocking in that any two idle customer terminals are always connectable regardless of the array interconnection of the other terminals, the rectangular array is not a practical network in most applications due to the prohibitive cost of the large number of array crosspoints.
One known nonblocking network having significantly fewer crosspoints than a rectangular array is disclosed in the article by C. Clos, "A Study of Nonblocking Switching Networks," Bell System Technical Journal, March, 1953, pp. 406-424. The network described in the latter article is termed a strictly nonblocking network. A network which is rearrangably nonblocking is described in the article by V. E. Benes, "On Rearrangable 3-Stage Connecting Networks," Bell System Technical Journal, Vol. 41, No. 5, September, 1962, pp. 1481-1492. Another rearrangeable network is described in U.S. Pat. No. 4,038,638 issued to F. K. Hwang, on July 26, 1977. The previously described networks are all controlled by a central control unit normally a computer. The problem with a central control unit being responsible for the allocation of paths through a network is that the central control can become a bottleneck when the switching application requires the high-speed switching of packets. The reason is that such applications require very high reconfiguration rates, and the speed at which information is clocked through the data paths is not as important as the rate at which the switch paths can be reconfigured. The ability to rearrange also requires a global view of the status of the network which is also true of the Clos network described in the previously referenced article.
From the foregoing, it can be seen that there exists a need for a self-routing network which is nonblocking and yet does not require the performance of complex routing calculations at each node. In addition, this network should be readily expandable.